#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
///*
//		反转链表
//*/
//
////法一：创建新链表，头插原链表节点到新链表中
//
////创建一个新结点
//typedef struct ListNode ListNode;
//ListNode* buynode(int x)
//{
//    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
//    if (newnode == NULL)
//    {
//        perror("malloc");
//        exit(-1);
//    }
//    newnode->val = x;
//    newnode->next = NULL;
//    return newnode;
//}
////头插
//void pushfront(ListNode** phead, int x)
//{
//    assert(phead);
//    //创建一个新结点
//    ListNode* newnode = buynode(x);
//    newnode->next = *phead;
//    *phead = newnode;
//}
//
//struct ListNode* reverseList(struct ListNode* head)
//{
//    //如果head为空
//    if (head == NULL)
//    {
//        return NULL;
//    }
//
//    //head不为空，进行头插
//    ListNode* newhead = NULL;
//    while (head)
//    {
//        pushfront(&newhead, head->val);
//        head = head->next;
//    }
//    return newhead;
//}
//
////法二：创建三个指针，在原链表进行翻转
//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    //如果原链表为空，直接返回NULL
//    if (head == NULL)
//    {
//        return NULL;
//    }
//
//    //原链表不为空
//    ListNode* n1 = NULL;
//    ListNode* n2 = head;
//    ListNode* n3 = head->next;
//    while (n2)
//    {
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//        if (n3 != NULL)
//        {
//            n3 = n3->next;
//        }
//    }
//    return n1;
//}
//
//
//
///*
//        移除链表元素
//*/
//
////法一：
//typedef struct ListNode ListNode;
////创建新节点
//ListNode* buynode(int x)
//{
//    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
//    if (newnode == NULL)
//    {
//        perror("malloc");
//        exit(-1);
//    }
//    newnode->val = x;
//    newnode->next = NULL;
//    return newnode;
//}
//
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    //如果原链表为空，则返回空
//    if (head == NULL)
//    {
//        return NULL;
//    }
//
//    //原链表不为空，遍历原链表，将所有不为val值的节点尾插到新链表中
//    ListNode* newhead = NULL;
//    ListNode* newtail = NULL;
//    while (head)
//    {
//        //先判断该val与要删除的val值是否相同
//        if (head->val != val)
//        {
//            ListNode* newnode = buynode(head->val);
//            //如果新链表为空
//            if (newhead == NULL)
//            {
//                newhead = newnode;
//                newtail = newnode;
//            }
//            //新链表不为空
//            else
//            {
//                //尾插
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//            head = head->next;
//        }
//        //该val值与要删除的相同，head直接向后走
//        else
//        {
//            head = head->next;
//        }
//    }
//    return newhead;
//}
//
////法二：
//typedef struct ListNode ListNode;
//
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    //如果原链表为空，直接返回NULL
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    //原链表不为空
//    //遍历原链表
//    ListNode* newhead = NULL;
//    ListNode* newtail = NULL;
//    while (head)
//    {
//        if (head->val != val)
//        {
//            //不等于，将该结点尾插到新链表中
//            if (newhead == NULL)
//            {
//                //新链表为空
//                newhead = head;
//                newtail = head;
//            }
//            else
//            {
//                //新链表不为空
//                newtail->next = head;
//                newtail = head;
//            }
//        }
//        head = head->next;
//    }
//    //将尾节点的next指针置为空
//    if (newtail)
//    {
//        newtail->next = NULL;
//    }
//    return newhead;
//}
//
//
////法三：
//typedef struct ListNode ListNode;
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    //原链表为空，返回NULL
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    //原链表不为空
//    ListNode* pcur = head;
//    ListNode* prev = NULL;
//    while (pcur)
//    {
//        ListNode* next = pcur->next;
//        if (pcur->val == val)
//        {
//            //删除该节点
//            if (prev == NULL)
//            {
//                head = next;
//            }
//            else
//            {
//                prev->next = next;
//            }
//            free(pcur);
//            pcur = next;
//        }
//        else
//        {
//            //不删除该节点，继续遍历
//            prev = pcur;
//            pcur = next;
//        }
//    }
//    return head;
//}


/*
    环形链表，约瑟夫问题
*/
#include <stdlib.h>
struct ListNode
{
    int val;
    struct ListNode* next;
};

//创建节点
struct ListNode* Buynode(int x)
{
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    newnode->next = NULL;
    newnode->val = x;
    return newnode;
}

//创建环形链表
struct ListNode* CycleList(int x)
{
    //先创建第一个节点
    struct ListNode* phead = Buynode(1);//头节点
    struct ListNode* ptail = phead;//尾节点

    int i = 0;
    for (i = 2; i <= x; i++)
    {
        //创建节点
        ptail->next = Buynode(i);
        ptail = ptail->next;
    }
    //退出循环时，ptail->next指向的是NULL
    //要成环，ptail的next指针要指向phead
    ptail->next = phead;//成环

    return ptail;//返回尾节点
}
int ysf(int n, int m)
{
    //创建环形链表
    struct ListNode* prev = CycleList(n);
    struct ListNode* pcur = prev->next;
    int count = 1;

    //遍历该环形链表，进行报数
    while (prev->next != prev)
    {
        if (count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;//重新报数
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    int ret = prev->val;
    free(pcur);
    pcur = NULL;

    return ret;
}

int main()
{
    int ret = ysf(5,2);
    printf("%d\n", ret);
    return 0;
}